package 二叉搜索树中的众数;

import java.util.*;

public class Solution {

    int maxCount = 0;
    int nowCount = 0;
    TreeNode pre = null;
    public int[] findMode(TreeNode root) {
        // 递归
        // 递归的参数：根节点,map->记录数字当前数字频次(Map维护)。需要两个全局变量进行维护：maxCount->记录最大频次，pre记录前一个节点。
        // 递归的返回值：无
        // 递归的终止条件：root == null
        // 单层递归逻辑：中序遍历是一个非递减的序列，使用中序遍历二叉搜索树，在处理根节点的时候，判断是否和
        // 前一节点的值相同。如果相同，则将当前数的出现频次加一。同时我们需要维护一个全局遍历 maxCount，
        // 用来记录当前的众数频次，如果发现当前的频次等于 maxCount，我们需要在结果集中新增一个当前数字
        // 如果发现当前的频次大于 maxCount，我们需要清除结果集，并将当前数字加入到结果集中。更新maxCount
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> result = new ArrayList<>();
        findModeByRecursion(root, result);
        return result.stream().mapToInt(Integer::valueOf).toArray();
    }

    public void findModeByRecursion(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        // left
        findModeByRecursion(root.left, result);
        // inorder
        // 计数
        if (pre == null || pre.val != root.val){
            nowCount = 1;
        }else{
            nowCount++;
        }
        // 更新结果集
        if (nowCount == maxCount) {
            result.add(root.val);
        } else if (nowCount > maxCount) {
            result.clear();
            result.add(root.val);
            maxCount = nowCount;
        }
        pre = root;
        // right
        findModeByRecursion(root.right, result);
    }
}
